二叉树的锯齿形层次遍历

发表于 | 分类于 |
字数统计: 739 字 | 阅读时长 ≈ 3 分钟

题目描述：给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：
给定二叉树 [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回锯齿形层序遍历如下：
[
[3],
[20,9],
[15,7]
]

方法一：BFS

  • 对树进行逐层遍历，用队列维护当前层的所有元素，当队列不为空的时候，求得当前队列的长度 size，每次从队列中取出 size 个元素进行拓展，然后进行下一次迭代。
  • 使用双端队列维护当前层节点值输出的顺序
    • 如果从左至右，我们每次将被遍历到的元素插入至双端队列的末尾。
    • 如果从右至左，我们每次将被遍历到的元素插入至双端队列的头部。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
  public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if(root == null) return res;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    Boolean odd = true;
    while(!queue.isEmpty()) {
      int size = queue.size();
      Deque<Integer> level = new LinkedList<Integer>(); // 与层级便利不同，使用双端队列维护
      while(size-- > 0) {
        TreeNode node = queue.poll();
        if(odd) {
          level.offerLast(node.val);
        } else {
          level.offerFirst(node.val);
        }
        if(node.left != null) {
          queue.offer(node.left);
        }
        if(node.right != null) {
          queue.offer(node.right);
        }
      }
      odd = !odd;
      res.add(new LinkedList<Integer>(level)); // 与层级便利不同
    }
    return res;
  }
}

var zigzagLevelOrder = function(root) {
  let res = []
  if(root === null) return res
    
  let queue = []
  queue.push(root)
  let isOdd = true
  while(queue.length) {
      let len = queue.length
      let level = []
      while(len--) {
          let node = queue.shift()
          if(isOdd) {
            level.push(node.val)
          } else {
            level.unshift(node.val)
          }
          if(node.left !== null) {
              queue.push(node.left)
          }
          if(node.right !== null) {
              queue.push(node.right)
          }
      }
      res.push(level)
      isOdd = !isOdd
  }
  return res
};

复杂度分析

  • 时间复杂度：O(n)，每个点进队出队各一次，故渐进时间复杂度为 O(n)
  • 空间复杂度：O(n)，我们需要维护存储节点的队列和存储节点值的双端队列，空间复杂度为 O(N)。

执行结果：通过

  • 执行用时：1 ms, 在所有 Java 提交中击败了97.49%的用户

  • 内存消耗：38.6 MB, 在所有 Java 提交中击败了37.34%的用户

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var zigzagLevelOrder = function(root) {
  let res = []
  if(root === null) return res
  dfs(1, root, res)
  return res
};

var dfs = function(level, root, res) {
  if(res.length < level) {
    res.push([])
  }
  if(level % 2 !== 0) {
    res[level - 1].push(root.val)
  } else {
    res[level - 1].unshift(root.val)
  }
  if(root.left !== null) {
    dfs(level + 1, root.left, res)
  }
  if(root.right !== null) {
    dfs(level + 1, root.right, res)
  }
  return
}

复杂度分析

  • 时间复杂度：O(N)
  • 空间复杂度：O(h)，h 是树的高度